#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <limits>
#include "conio.h"

using namespace std;

// table[i][j] - max length of common substring, that ends in positions i and j
int longest_common_substring(string s1, string s2)
{
	vector<vector<int>> table(s1.size(), s2.size());	
	int subseq_end_1 = -1,
		subseq_end_2 = -1;
	int max_len = numeric_limits<int>::min();

	for (int i = 0; i < s1.size(); ++i)
	{
		for (int j = 0; j < s2.size(); ++j)
		{
			if (s1[i] == s2[j])
			{
				if (i == 0 || j == 0)
				{
					table[i][j] = 1;
				}
				else
				{
					table[i][j] = table[i-1][j-1] + 1;
					if (max_len < table[i][j])
					{
						max_len = table[i][j];
						subseq_end_1 = i;
						subseq_end_2 = j;
					}
				}
			}
			else
				table[i][j] = 0;
		}
	}

	cout << "Common substring: " << endl;
	for (int i = subseq_end_1, j = subseq_end_2; i >= 0; --i, --j)
		if (s1[i] == s2[j]) 
			cout << s1[i] << " ";

	return max_len;
}

void main()
{
	string s1, s2;
	
	cout << "input first string: " << endl;
	cin >> s1;		
	cout << "input second string: " << endl;
	cin >> s2;	

	cout << endl << "length of the LCS = " << longest_common_substring(s1, s2);
	_getch();
}